import java.util.*;

/**
 * 710. 黑名单中的随机数
 * https://leetcode-cn.com/problems/random-pick-with-blacklist/
 */
public class Solutions_710 {
    public static void main(String[] args) {
        int n = 6;
        int[] blacklist = {0, 5};
        Solution_710 solution = new Solution_710(n, blacklist);
        int res1 = solution.pick();
        System.out.println(res1);
        int res2 = solution.pick();
        System.out.println(res2);
        int res3 = solution.pick();
        System.out.println(res3);
        int res4 = solution.pick();
        System.out.println(res4);
        int res5 = solution.pick();
        System.out.println(res5);
        int res6 = solution.pick();
        System.out.println(res6);
    }
}

class Solution_710 {

    /**
     * 记录白名单的数字
     */
    private Set<Integer> whiteNums;

    /**
     * 映射表：将黑名单中的数字映射为白名单的数字
     */
    private Map<Integer, Integer> map;
    private Random random;

    /**
     * 白名单的长度
     */
    private int whiteLen;

    public Solution_710(int n, int[] blacklist) {
        map = new HashMap<>();
        whiteNums = new HashSet<>();
        random = new Random();

        whiteLen = n - blacklist.length;
        for (int i = whiteLen; i < n; i++) {
            whiteNums.add(i);
        }
        for (int num : blacklist) {
            // 白名单中移除黑名单中的数字
            whiteNums.remove(num);
        }
        Iterator<Integer> iterator = whiteNums.iterator();
        for (int num : blacklist) {
            if (num < whiteLen) {
                // 进行映射
                map.put(num, iterator.next());
            }
        }
    }

    public int pick() {
        int n = random.nextInt(whiteLen);
        // 有映射则取映射，无映射则取数字本身
        int res = map.getOrDefault(n, n);
        return res;
    }

}
